package junior.回溯法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;







public class Combination_II {
    static int[] a;
    static int startIndex;
    static List<Integer> list;
    public static void main(String[] args) {
        a = new int[]{1, 2, 1};
        startIndex = 0;
        list = new ArrayList<>();
        Arrays.sort(a);
    }
    /**
     * 有重复元素的列表【n个元素，取全部的子集】
     */
    public static void dfs1(int startIndex){
        if(list.size() == a.length){
            return;
        }
        for (int i = startIndex; i < a.length; i++) {
            if(i > startIndex && a[i-1] == a[i]){ // 行去重，
                continue;
            }
            list.add(a[i]);  // 每添加一个合法元素，该集合就是一个合法的子集列表（排序 + startIndex -> 元素去重）
            System.out.println("list.toString() = " + list.toString());
            dfs1(i+1);
            list.remove(list.size()-1);

        }
    }
    /**
     * 有重复元素的列表【n个元素，取k个的组合】
     */
    public static void dfs0(int startIndex){
        if(list.size() == a.length-1){
            System.out.println("list.toString() = " + list.toString());
            return;
        }
        for (int i = startIndex; i < a.length; i++) {
            if(i > startIndex && a[i-1] == a[i]){
                continue;
            }
            list.add(a[i]);
            dfs0(i+1);
            list.remove(list.size()-1);

        }
    }
}
